package com.example;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #39. 组合总和
 * @Date 2019/11/27 9:18 下午
 */
public class CombinationSum {
/*
    public List<List<Integer>> lists = new ArrayList<>();

    *//**
     * @Author loubobooo
     * @Description 给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
     * candidates中的数字可以无限制重复被选取。
     * 说明：
     * 所有数字（包括 target）都是正整数。
     * 解集不能包含重复的组合。
     * @Date 2019/11/27 9:24 下午
     * @Param
     * @return
     **//*
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates == null || candidates.length < 1){
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        processOn(0, candidates, target, list);
        return lists;
    }

    public void processOn(int start, int[] candidates, int target, List<Integer> list){
        // 每次循环递归target-candidates[i]值
        if(target < 0){
            return;
        }else if(target == 0){
            lists.add(new ArrayList<>(list));
        }else{
            for (int i = start, length = candidates.length; i < length; i++) {
                // 每次都添加数组中这个值进list中
                list.add(candidates[i]);
                // 循环递归传值
                processOn(i, candidates, target - candidates[i], list);
                list.remove(list.size() - 1);
            }
        }
    }*/

    private List<List<Integer>> lists = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates == null || candidates.length < 1){
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        backTracking(0, candidates, target, list);
        return lists;
    }

    private void backTracking(int start, int[] candidates, int target, List<Integer> list){
        // 设置终止条件
        if(target < 0){
            return;
        }else if(0== target){
            // 添加元素
            lists.add(new ArrayList<>(list));
        }else{
            // 遍历
            for (int i = start; i < candidates.length; i++) {
                // 处理节点
                list.add(candidates[i]);
                // 递归
                backTracking(i, candidates, target - candidates[i], list);
                // 回撤节点（剪枝）
                list.remove(list.size() - 1);
            }
        }
    }


    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 7};
        int target = 7;
        CombinationSum combinationSum = new CombinationSum();
        List<List<Integer>> lists = combinationSum.combinationSum(nums, target);
        for (List<Integer> l: lists) {
            for (Integer i: l) {
                System.out.print(i + ",");
            }
            System.out.println("===================");
        }
    }
}
